package com.jiang.专题.动态规划.Q64;

/**
 * @author Jiang
 * @version 1.0
 * @date 2024/12/25 20:41
 */
class Solution {
    // 二维数组
    // public int minPathSum(int[][] grid) {
    //     int m = grid.length;
    //     int n = grid[0].length;
    //     for (int i = 1; i < m; i++) {
    //         grid[i][0] += grid[i - 1][0]; // 第一列中，每个元素的最小路径为当前路径 + 上边一个元素的路径
    //     }
    //     for (int i = 1; i < n; i++) {
    //         grid[0][i] += grid[0][i - 1]; // 第一行中，每个元素的最小路径为当前路径 + 左边一个元素的路径
    //     }
    //     for (int i = 1; i < m; i++) {
    //         for (int j = 1; j < n; j++) {
    //             grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]); // 其余元素的最小路径为当前路径 + 上边或左边较小的路径
    //         }
    //     }
    //     return grid[m - 1][n - 1];
    // }

    // 一维数组
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[] dp = new int[n];
        dp[0] = grid[0][0]; // dp数组保存每一行元素的最小路径
        for (int i = 1; i < n; i++) {
            dp[i] = dp[i - 1] + grid[0][i]; // dp数组保存第一行每个元素的最小路径
        }
        for (int i = 1; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (j == 0) {
                    dp[0] += grid[i][j]; // dp[0]表示第一列第i + 1行元素的最小路径
                } else {
                    dp[j] = Math.min(dp[j - 1], dp[j]) + grid[i][j]; // dp[j] 表示第i + 1行第j + 1列元素的最小路径，是由dp[j - 1]矩阵左边元素 或 dp`[j]矩阵上边元素较小的路径 + 当前元素路径得来
                }
            }
        }
        return dp[n - 1];
    }
}
